#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

int qucik_one_pass(int arr[], int low, int high) {
    int i = low , j = high;
    int pivotkey = arr[i];  // 枢轴元素
    while (i < j) {
        // 从右往左找到第一个小于枢轴元素的元素
        while (pivotkey < arr[j] && j > i) {
            j--;
        }
        if(j > i){
            arr[i] = arr[j];
            i++;
        }
        while (arr[i] < pivotkey && i < j)
            i++;
        if(j > i){
            arr[j] = arr[i];
            j--;
        }
    }
    arr[i] = pivotkey;
    return i;
}

// 快速排序
void QuickSort(int arr[], int low, int high) {
    int k;
    if (low < high) {
        k = qucik_one_pass(arr, low, high);  // 划分，得到枢轴元素的位置
        QuickSort(arr, low, k - 1);  // 对枢轴元素左边的子序列进行快速排序
        QuickSort(arr, k + 1, high);  // 对枢轴元素右边的子序列进行快速排序
    }
}

// 打印数组
void PrintArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 检查数组是否已排序
int IsSorted(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        if (arr[i] < arr[i-1]) {
            return 0;  // 未排序
        }
    }
    return 1;  // 已排序
}

// 复制数组
void CopyArray(int src[], int dest[], int n) {
    for (int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

// 生成随机数组
void GenerateRandomArray(int arr[], int n, int max_val) {
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % max_val + 1;
    }
}

// 测试单个数组的快速排序
void TestQuickSort(int original[], int n, const char* testName) {
    int arr[n];
    
    printf("=== %s ===\n", testName);
    printf("原始数组: ");
    PrintArray(original, n);
    
    // 复制数组并排序
    CopyArray(original, arr, n);
    QuickSort(arr, 0, n - 1);
    
    printf("排序后: ");
    PrintArray(arr, n);
    printf("排序正确性: %s\n", IsSorted(arr, n) ? "✓ 正确" : "✗ 错误");
    printf("\n");
}

// 详细步骤演示（小数组）
void DemoQuickSortSteps(int arr[], int n) {
    printf("=== 快速排序步骤演示 ===\n");
    printf("原始数组: ");
    PrintArray(arr, n);
    
    // 手动演示第一次划分
    printf("第一次划分过程:\n");
    printf("选择枢轴: %d (第一个元素)\n", arr[0]);
    
    int pivot_pos = qucik_one_pass(arr, 0, n - 1);
    printf("划分后: ");
    PrintArray(arr, n);
    printf("枢轴位置: %d, 枢轴值: %d\n", pivot_pos, arr[pivot_pos]);
    printf("左子序列: 索引 0 到 %d\n", pivot_pos - 1);
    printf("右子序列: 索引 %d 到 %d\n", pivot_pos + 1, n - 1);
    
    // 完成剩余排序
    QuickSort(arr, 0, pivot_pos - 1);
    QuickSort(arr, pivot_pos + 1, n - 1);
    
    printf("最终结果: ");
    PrintArray(arr, n);
    printf("\n");
}

// 主测试函数
void TestQuickSortComprehensive() {
    printf("========== 快速排序全面测试 ==========\n\n");
    
    // 测试用例1：一般情况
    int test1[] = {64, 34, 25, 12, 22, 11, 90};
    int n1 = sizeof(test1) / sizeof(test1[0]);
    TestQuickSort(test1, n1, "测试1：一般情况");
    
    // 测试用例2：已排序数组
    int test2[] = {1, 2, 3, 4, 5, 6, 7};
    int n2 = sizeof(test2) / sizeof(test2[0]);
    TestQuickSort(test2, n2, "测试2：已排序数组");
    
    // 测试用例3：逆序数组
    int test3[] = {7, 6, 5, 4, 3, 2, 1};
    int n3 = sizeof(test3) / sizeof(test3[0]);
    TestQuickSort(test3, n3, "测试3：逆序数组");
    
    // 测试用例4：重复元素
    int test4[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int n4 = sizeof(test4) / sizeof(test4[0]);
    TestQuickSort(test4, n4, "测试4：重复元素");
    
    // 测试用例5：单个元素
    int test5[] = {42};
    int n5 = sizeof(test5) / sizeof(test5[0]);
    TestQuickSort(test5, n5, "测试5：单个元素");
    
    // 测试用例6：两个元素
    int test6[] = {2, 1};
    int n6 = sizeof(test6) / sizeof(test6[0]);
    TestQuickSort(test6, n6, "测试6：两个元素");
    
    // 演示步骤
    int demo[] = {5, 2, 8, 1, 9, 3};
    int demo_n = sizeof(demo) / sizeof(demo[0]);
    DemoQuickSortSteps(demo, demo_n);
    
    // 性能测试：大数组
    printf("=== 性能测试：大数组 ===\n");
    const int large_size = 10000;
    int *large_array = (int*)malloc(large_size * sizeof(int));
    
    if (large_array != NULL) {
        GenerateRandomArray(large_array, large_size, 10000);
        QuickSort(large_array, 0, large_size - 1);
        
        printf("数组大小: %d 个元素\n", large_size);
        printf("排序正确性: %s\n", IsSorted(large_array, large_size) ? "✓ 正确" : "✗ 错误");
        
        free(large_array);
    }

}

// 主函数
int main() {
    TestQuickSortComprehensive();
    return 0;
}
